﻿using System;
using System.Net;
using System.Collections.Generic;

namespace BaseArith {
    public class Graph<T> {
        /// <summary>
        /// 图包含节点
        /// </summary>
        public List<Node<T>> Nodes;
        public Graph() {
            Nodes = new List<Node<T>>();
        }
    }

    public class Node<T> {
        /// <summary>
        /// 节点值
        /// </summary>
        public T Value;
        /// <summary>
        /// 是否被访问过
        /// </summary>
        public bool IsVisited;
        /// <summary>
        /// 关系节点
        /// </summary>
        public List<Node<T>> AssociatedNodes;
        public int Index { get; set; }

        public Node(T value) {
            Value = value;
            IsVisited = false;
            AssociatedNodes = new List<Node<T>>();
        }
    }

    public class GraphFactory<T> {
        /// <summary>
        /// 创建一个简单的关系图
        /// </summary>
        /// <returns></returns>
        public static Graph<int> CreateSimpleGraph() {
            Graph<int> graph = new Graph<int>();
            int len = 6;
            int i = 1;
            //图中有len个节点
            for (i = 0; i < len; i++)
                graph.Nodes.Add(new Node<int>(i));

            //随机创建40条边，可重复
            Random random = new Random();
            for (i = 0; i < 10; i++) {
                int n1 = random.Next(0, len);
                int n2 = random.Next(0, len);
                //如果随机到相同的点
                if (n1 == n2)
                    n2 = (n1 + 1) % len;
                graph.Nodes[n1].AssociatedNodes.Add(graph.Nodes[n2]);
                graph.Nodes[n2].AssociatedNodes.Add(graph.Nodes[n1]);
            }

            return graph;
        }

        /// <summary>
        /// 深度优先遍历
        /// </summary>
        /// <param name="graph"></param>
        public static void DepthFirstTraversal(Graph<T> graph) {
            Reset(graph);
            if (graph.Nodes.Count == 0)
                return;
            Node<T> node = GetNodeUnVisited(graph);
            while (node != null) {
                DepthFirstTraversal_Node(node);
                node = GetNodeUnVisited(graph);
            }
        }

        /// <summary>
        /// 广度优先遍历
        /// </summary>
        /// <param name="graph"></param>
        public static void BreadthFirstTraversal(Graph<T> graph) {
            Reset(graph);
            if (graph.Nodes.Count == 0)
                return;
            Node<T> node = GetNodeUnVisited(graph);
            Queue<Node<T>> nodequeue = new Queue<Node<T>>();
            while (node != null) {
                BreadthFirstTraversal_Node(node, nodequeue);
                node = nodequeue.Dequeue();
                if (node == null)
                    node = GetNodeUnVisited(graph);
            }
        }
        /// <summary>
        /// 广度优先遍历节点
        /// 访问该节点(如果该节点未被访问)，然后将其关系节点(如果该节点未被访问)放入队列中
        /// </summary>
        /// <param name="node"></param>
        /// <param name="nodequeue"></param>
        private static IEnumerable<T> BreadthFirstTraversal_Node(Node<T> node, Queue<Node<T>> nodequeue) {
            if (!(node.IsVisited || node == null)) {
                node.IsVisited = true;
                yield return node.Value;
                foreach (Node<T> n in node.AssociatedNodes) {
                    if (!n.IsVisited)
                        nodequeue.Enqueue(n);
                }
            }
        }
        /// <summary>
        /// 深度优先遍历节点
        /// 先访问该节点，然后递归其关系节点
        /// </summary>
        /// <param name="node"></param>
        private static IEnumerable<T> DepthFirstTraversal_Node(Node<T> node) {
            if (!(node.IsVisited || node == null)) {
                node.IsVisited = true;
                yield return node.Value;
                foreach (Node<T> associatednode in node.AssociatedNodes) {
                    DepthFirstTraversal_Node(associatednode);
                }
            }
        }
        /// <summary>
        /// 获取图中一个未访问的节点
        /// </summary>
        /// <param name="graph"></param>
        /// <returns></returns>
        private static Node<T> GetNodeUnVisited(Graph<T> graph) {
            foreach (Node<T> node in graph.Nodes)
                if (!node.IsVisited)
                    return node;
            return null;
        }
        /// <summary>
        /// 重新设置图中各节点的访问状态为false
        /// </summary>
        /// <param name="graph"></param>
        private static void Reset(Graph<T> graph) {
            foreach (Node<T> node in graph.Nodes)
                node.IsVisited = false;
        }
    }

}
